﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定⼀个n个元素有序的（升序）整型数组nums和⼀个⽬标值target，写⼀个函数搜索nums中的target，如果⽬标值存在返回下标，否则返回 - 1
//eg:输⼊:nums = [-1, 0, 3, 5, 9, 12], target=9  返回：4
#include <iostream>
using namespace std;

int search(int* a,int n,int t)
{
	// 初始化 left 与 right 指针
	int left = 0, right = n - 1;
	while(left<=right)// 由于两个指针相交时，当前元素还未判断，因此需要取等号
	{
		int mid = left + (right - left) / 2;//取中位数，为避免数据溢出这样写
		if (a[mid] < t)
			left = mid + 1;
		else if (a[mid] > t)
			right = mid - 1;
		else
			return mid;
	}
	return -1;
}

int main()
{
	int nums[] = { -1, 0, 3, 5, 9, 12 },target=49;
	int n = sizeof(nums) / sizeof(nums[0]);
	for (int i = 0; i < n; i++)
	{
		cout << nums[i] << ' ';
	}
	cout << endl;

	int an = search(nums, n,target);
	cout << an << endl;

	return 0;
}